package linkedlist.test143;

import listbyorder.utils.ListNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/14 13:52
 */
public class Solution1 {

    public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) return;
        // 快慢指针找到中间节点
        ListNode s = head, f = head;
        while (f != null && f.next != null) {
            s = s.next;
            f = f.next.next;
        }
        ListNode cha = reverse(s.next);
        s.next = null;
        ListNode t = head;
        ListNode a, b;
        while (cha != null) {
            a = t.next;
            b = cha.next;
            t.next = cha;
            cha.next = a;
            t = a;
            cha = b;
        }
    }

    private ListNode reverse(ListNode node) {
        ListNode pre = null;
        ListNode next;
        while (node != null) {
            next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }
}
